home *** CD-ROM | disk | FTP | other *** search
/ Aminet 28 / Aminet 28 (1998)(GTI - Schatztruhe)[!][Dec 1998].iso / Aminet / dev / c / qtools0.2-src.lha / src / liblists / liblists.c next >
Encoding:
C/C++ Source or Header  |  1998-07-13  |  24.3 KB  |  727 lines
  1. #ifndef LISTS_C
  2. #define LISTS_C
  3.  
  4. /* Name : list.c
  5.  *
  6.  * Notes: The following passage is taken verbatim from _Amiga_ROM_Kernal
  7.  *        _Reference_Manual:_Libraries_3rd_Edition_, page 490
  8.  *
  9.  * One subtlety here must be explained further.  The list header is
  10.  * constructed in an efficient, but confusing manner.  This of the header
  11.  * as a structure containg the head and tail nodes for the list.  The
  12.  * head and tail nodes are placeholders, and never carry data.  The head
  13.  * and tail portions of the header actually overlap in memory.  lh_Head and
  14.  * lh_Tail form the head node; lh_Tail and lh_TailPred form the tail node.
  15.  * This makes it easy to find the start or end of the list, and eliminates
  16.  * any special cases for insertion or removal.
  17.  *
  18.  *   "Head Node"   "Tail Node"         "Merged Header"
  19.  * +-------------+                     +-------------+
  20.  * |   ln_Succ   |                     |   lh_Head   |
  21.  * +-------------+-------------+       +-------------+
  22.  * | ln_Pred = 0 | ln_Succ = 0 |  ---> | lh_Tail = 0 |
  23.  * +-------------+-------------+       +-------------+
  24.  *               |   ln_Pred   |       | ln_TailPred |
  25.  *               +-------------+       +-------------+
  26.  *
  27.  *           Figure 23-2: List Header Overlap
  28.  *
  29.  * The lh_Head and lh_Tail fields of the list header act like the
  30.  * ln_Succ and lh_Pred fields of a node.  The lh_Tail field is set
  31.  * permanently to NULL, indicating that the head node is indeed the
  32.  * first on the list -- that is, it has no predecessors.
  33.  *
  34.  * Likewise, the lh_Tail and lh_TailPred fields of the list header
  35.  * act like the ln_Succ and ln_Pred fields of a node.  Here the NULL
  36.  * lh_Tail indicates that the tail node is indeed the list on the
  37.  * list -- that is, it has no successors.
  38.  *
  39.  *      $Log:   list.c,v $
  40.  * Revision 2.0  98/07/09  04:57:56  nf
  41.  * Completely rewritten, only the comments left for documentation
  42.  * added FindNode and different faster SortLists
  43.  *
  44.  * Revision 1.4  95/10/26  16:17:42  idr
  45.  * Changed FindName() to use a slightly more optimal loop condition.
  46.  * Changed SortList() to use a radix sort rather than the yucky sort
  47.  * that it was using before.  At this time, the old versions of both
  48.  * functions still exist in the code.
  49.  * 
  50.  * Revision 1.3  95/10/20  15:03:47  idr
  51.  * Fixed a bug in the Enqueue() function that caused nodes to be added to
  52.  * the list in the wrong order.  I also cleaned that function and a couple
  53.  * of others up a little bit so that they're a bit easier to read.
  54.  * 
  55.  * Revision 1.2  1995/09/05  02:38:01  idr
  56.  * Move AddHead() and AddTail() so that I would not need to use any
  57.  * bounus function prototypes to prevent compliation errors.
  58.  *
  59.  * Revision 1.1  1995/07/09  20:10:47  idr
  60.  * Initial revision
  61.  */
  62.  
  63. #include <math.h>
  64. #include <stdlib.h>
  65. #include <string.h>
  66. #include <liblists.h>
  67.  
  68. /*
  69.  * some list management
  70.  */
  71.  
  72. /******************************************************************************/
  73. /* Name : NewList()
  74.  *
  75.  * Notes: The following passage is taken verbatim from _Amiga_ROM_Kernal
  76.  *        _Reference_Manual:_Libraries_3rd_Edition_, page 490
  77.  *
  78.  * HEADER INITIALIZATION
  79.  *
  80.  * List headers must be properly initialized before use.  It is not
  81.  * adequate to initialize the entire header to zero.  The head and tail
  82.  * entries must have specific values.  The header must be initialized
  83.  * as follows:
  84.  *
  85.  *  1. Set the lh_Head field to the address of lh_Tail.
  86.  *  2. Clear the lh_Tail field.
  87.  *  3. Set the lh_TailPred field to the address of lh_Head.
  88.  *  4. Set lh_Type to the same data type as the nodes to be kept
  89.  *     in the list. (Unless you are using a MinList).
  90.  */
  91. void nNewList(struct nlist *list)
  92. {
  93.   list->head = (struct nnode *)&(list->tail);
  94.   list->tail = NULL;
  95.   list->tailpred = (struct nnode *)&(list->head);
  96.   list->nodes = 0;
  97. }
  98.  
  99. /******************************************************************************/
  100. /* Name : AddHead()
  101.  *
  102.  * Notes: This function adds the specified node to the begining (head)
  103.  *        of the specified list.
  104.  */
  105. void nAddHead(struct nlist *list, struct nnode *node)
  106. {
  107.   /* temporary pointer to a node  */
  108.   struct nnode *tempnode;
  109.  
  110.   /* Save the pointer to the old head node. */
  111.   tempnode = list->head;
  112.   /* Make ``node'' the new head. */
  113.   list->head = node;
  114.   /* Link ``node'' to its new neighbors. */
  115.   node->succ = tempnode;
  116.   node->pred = (struct nnode *)list;
  117.   /* Link the old head to the new head. */
  118.   tempnode->pred = node;
  119.   list->nodes++;
  120. }
  121.  
  122. /******************************************************************************/
  123. /* Name : AddTail()
  124.  *
  125.  * Notes: This function adds the specified node to the end (tail) of
  126.  *        the given list.
  127.  */
  128. void nAddTail(struct nlist *list, struct nnode *node)
  129. {
  130.   struct nnode *tempnode;                    /* temporary pointer to a node    */
  131.   struct nnode *tailnode;                    /* pointer to the tail part of the list */
  132.  
  133.   /* Get a pointer to the tail part of the list header so that
  134.    * we can just treat it like a normal node. 
  135.    */
  136.   tailnode = (struct nnode *)&(list->tail);
  137.   /* Save a pointer to the old tail node. */
  138.   tempnode = tailnode->pred;
  139.   /* Set the new tail node pointer. */
  140.   tailnode->pred = node;
  141.   /* Link the new tail node to its new neighbors. */
  142.   node->pred = tempnode;
  143.   node->succ = tailnode;
  144.   /* Line the old tail node to its new neighbors. */
  145.   tempnode->succ = node;
  146.   list->nodes++;
  147. }
  148.  
  149. /******************************************************************************/
  150. /* Name : RemHead()
  151.  *
  152.  * Notes: This function unlinks and returns the head node in the
  153.  *        given list.  If the list is empty, this function will
  154.  *        return NULL.
  155.  */
  156. struct nnode *nRemHead(struct nlist *list)
  157. {
  158.   struct nnode *headnode;                    /* pointer to the old head of the list  */
  159.   struct nnode *tempnode;                    /* pointer to temporary node   */
  160.  
  161.   /* If the head node is the list node in the list, then
  162.    * the list is really empty (see header comment for why
  163.    * this is the case), so we need to return NULL. 
  164.    */
  165.   if (list->nodes == 0)
  166.     return (NULL);
  167.   /* Get a pointer to the old head of the list. */
  168.   headnode = list->head;
  169.   /* Get the node after the old head. */
  170.   tempnode = headnode->succ;
  171.   /* Link the header and the node after the old head node
  172.    * to each other. 
  173.    */
  174.   list->head = tempnode;
  175.   tempnode->pred = (struct nnode *)list;
  176.   /* Unlink the old head from the list. */
  177.   headnode->succ = headnode->pred = NULL;
  178.   /* Return the old head. */
  179.   list->nodes--;
  180.   return (headnode);
  181. }
  182.  
  183. /******************************************************************************/
  184. /* Name : RemTail()
  185.  *
  186.  * Notes: This function unlinks and returns the tail node in the
  187.  *        given list.  If the list is empty, this function will
  188.  *        return NULL.
  189.  */
  190. struct nnode *nRemTail(struct nlist *list)
  191. {
  192.   struct nnode *tailnode;                    /* pointer to the old tail of the list  */
  193.   struct nnode *tempnode;                    /* pointer to temporary node   */
  194.  
  195.   if (list->nodes == 0)
  196.     return (NULL);
  197.   tailnode = list->tailpred;
  198.   tempnode = tailnode->pred;
  199.   list->tailpred = tempnode;
  200.   tempnode->succ = (struct nnode *)&(list->tail);
  201.   list->nodes--;
  202.   return (tailnode);
  203. }
  204.  
  205. /******************************************************************************/
  206. /* Name : Remove()
  207.  *
  208.  * Notes: The following passage is taken verbatim from _Amiga_ROM_Kernal
  209.  *        _Reference_Manual:_Libraries_3rd_Edition_, page 492
  210.  *
  211.  * The Remove() function is used to remove a specified node from a list.
  212.  * For example, Remove(node) will remove the specified node from whatever
  213.  * list it is in.  To be removed, a node must actually be in a list.  If
  214.  * you attempt to remove a node that is not in a list, you will cause
  215.  * serious system problems.
  216.  */
  217. void nRemove(struct nlist *list, struct nnode *node)
  218. {
  219.   /* Line the node's neighbors to each other, rather than to node. */
  220.   node->pred->succ = node->succ;
  221.   node->succ->pred = node->pred;
  222.   /* Unlink the node's neighbors from the node. */
  223.   node->succ = node->pred = NULL;
  224.   list->nodes--;
  225.   return;
  226. }
  227.  
  228. /******************************************************************************/
  229. /* Name : Insert()
  230.  *
  231.  * Notes: The following passage is taken verbatim from _Amiga_ROM_Kernal
  232.  *        _Reference_Manual:_Libraries_3rd_Edition_, page 492
  233.  *
  234.  * The Insert() function is used for inserting a new node into any
  235.  * position in a list.  It always inserts the node following a
  236.  * specified node that is already part of the list.  For example,
  237.  * Insert(header, node, pred) inserts the node ``node'' after the node
  238.  * ``pred'' in the specified list.  If the pred node points to the list
  239.  * header or is NULL, the new node will be inserted at the head of the
  240.  * list.  Similarly, if the pred node points to the lh_Tail of the
  241.  * list, the new node will be inserted at the tail of the list.  However,
  242.  * both of these actions can be better accomplished with the functions
  243.  * mentioned in the "Special Case Insertion" section below.
  244.  */
  245. void nInsert(struct nlist *list, struct nnode *node, struct nnode *pred)
  246. {
  247.   struct nnode *tempnode;                    /* temporary pointer to a node  */
  248.  
  249.   /* If the pointer to ``pred'' is NULL, then ``node'' will become
  250.    * the head of the list. 
  251.    */
  252.   if (pred == NULL) {
  253.     nAddHead(list, node);
  254.   }
  255.   else {
  256.     /* Save the pointer to the node that comes after ``pred''. */
  257.     tempnode = pred->succ;
  258.     /* Link ``pred'' to its new successor. */
  259.     pred->succ = node;
  260.     /* Link ``node'' to its new neighbors. */
  261.     node->pred = pred;
  262.     node->succ = tempnode;
  263.     /* Link pred's old successor back to its new predicessor. */
  264.     tempnode->pred = node;
  265.     list->nodes++;
  266.   }
  267. }
  268.  
  269. /******************************************************************************/
  270. /* Name : preInsert()
  271.  *
  272.  * Notes: The preInsert() function is used for inserting a new node into any
  273.  *        position in a list.  It always inserts the node preceding a
  274.  *        specified node that is already part of the list.  For example,
  275.  *        Insert(header, node, succ) inserts the node ``node'' before the node
  276.  *        ``succ'' in the specified list.  If the succ node points to the list
  277.  *        header or is NULL, the new node will be inserted at the head of the
  278.  *        list.  Similarly, if the succ node points to the lh_Tail of the
  279.  *        list, the new node will be inserted at the tail of the list.
  280.  *        However, both of these actions can be better accomplished with the
  281.  *        functions mentioned in the "Special Case Insertion" section below.
  282.  */
  283. void npreInsert(struct nlist *list, struct nnode *node, struct nnode *succ)
  284. {
  285.   struct nnode *tempnode;                    /* temporary pointer to a node  */
  286.  
  287.   /* If the pointer to ``succ'' is NULL, then ``node'' will become
  288.    * the head of the list. 
  289.    */
  290.   if ((succ == NULL) || (succ->pred == NULL)) {
  291.     nAddHead(list, node);
  292.   }
  293.   else {
  294.     /* Save the pointer to the node that comes before ``succ''. */
  295.     tempnode = succ->pred;
  296.     /* Link ``pred'' to its new Predecessor */
  297.     succ->pred = node;
  298.     /* Link ``node'' to its new neighbors. */
  299.     node->succ = succ;
  300.     node->pred = tempnode;
  301.     /* Link pred's old predecesor back to its new successor. */
  302.     tempnode->succ = node;
  303.     list->nodes++;
  304.   }
  305. }
  306.  
  307. /******************************************************************************/
  308. /* Name : Enqueue()
  309.  *
  310.  * Notes: The following passage is taken verbatim from _Amiga_ROM_Kernal
  311.  *        _Reference_Manual:_Libraries_3rd_Edition_, page 492
  312.  *
  313.  * PRIORITIZED INSERTION
  314.  *
  315.  * The list functions discussed so far do not make use of the priority
  316.  * field in a Node.  The Enqueue() function is equivalent to Insert(),
  317.  * except that it inserts nodes into a list sorting them according to
  318.  * their priority.  It keeps the higher-priority nodes towards the head
  319.  * of the list.  All nodes passed to this function must have their
  320.  * priority and name assigned prior to the call.  Enqueue(header, mynode)
  321.  * inserts ``mynode'' behind the lowest priority node with a priority
  322.  * greater than or qual to ``mynode's''.  For Enqueue() to work properly,
  323.  * the list ``mylist'' already be sorted according to priority.  Because the
  324.  * highest priority node is at the head of the list, the RemHead() function
  325.  * will remove the highest priority node.  Likewise, RemTail() will remove
  326.  * the lowest priority node.
  327.  *
  328.  *      FIFO Is Used For The Same Priority.  If you add a node that has
  329.  *      the same priority as another node in the queue, Enqueue() will
  330.  *      use FIFO ordering.  The new node is inserted following the list
  331.  *      node of equal priority.
  332.  */
  333. struct nnode *nFindNode(struct nlist *list, int data)
  334. {
  335.   register struct nnode *currnode = list->head;
  336.   register int middle;
  337.  
  338.   if ((middle = list->nodes - 1) > 0) {
  339.     register int i;
  340.  
  341.     for (i = middle; i >= 0; i--) {                /* real tries to find node is ln2(rgbnodes) */
  342.       /* find the middle */
  343.       register int shift = middle >> 1;
  344.       register int loop = shift;
  345.       register struct nnode *middnode = currnode;
  346.  
  347.       if (!loop)
  348.     break;
  349.       else {                            /* compare */
  350.     while ((loop--) > 0)                    /* this eats most of the time */
  351.       middnode = middnode->succ;
  352.  
  353.     if (data < middnode->data) {                /* if less than jump */
  354.       currnode = middnode;
  355.       middle = middle - shift;
  356.     }
  357.     else if (data > middnode->data)                /* if greater than stay */
  358.       middle = shift;
  359.     else
  360.       break;
  361.       }
  362.     }
  363.   }
  364.   else {
  365.     if (middle < 0)
  366.       currnode = 0;
  367.   }
  368.  
  369.   return currnode;
  370. }
  371.  
  372. void nEnqueue(struct nlist *list, struct nnode *node)
  373. {
  374.   int data = node->data;
  375.  
  376.   /* special case for empty list element */
  377.   if (list->nodes = 0)
  378.     nAddTail(list, node);
  379.   /* special case for first list element */
  380.   else if (data >= list->head->data)
  381.     nAddHead(list, node);
  382.   /* special case for last list element */
  383.   else if (data <= list->tailpred->data)
  384.     nAddTail(list, node);
  385.   /* we must walk the tree */
  386.   else
  387.     nInsert(list, node, nFindNode(list, data));
  388. }
  389.  
  390. /******************************************************************************/
  391. /* Name : GetHead()
  392.  *
  393.  * Notes: This function is very similar in concept to RemHead(), with the
  394.  *        exception that it doesn't modify the linked list.
  395.  */
  396. struct nnode *nGetHead(struct nlist *list)
  397. {
  398.   return ((list->head->succ == NULL) ? NULL : list->head);
  399. }
  400.  
  401. /******************************************************************************/
  402. /* Name : GetTail()
  403.  *
  404.  * Notes: This function is very similar in concept to RemTail(), with the
  405.  *        exception that it doesn't modify the linked list.
  406.  */
  407. struct nnode *nGetTail(struct nlist *list)
  408. {
  409.   return ((list->tailpred->pred == NULL) ? NULL : list->tailpred);
  410. }
  411.  
  412. /******************************************************************************/
  413. /* Name : SuccNode()
  414.  *
  415.  * Notes: This function returns a pointer to the next node, if one exists.
  416.  *
  417.  */
  418. struct nnode *nSuccNode(struct nnode *node)
  419. {
  420.   return ((node->succ->succ == NULL) ? NULL : node->succ);
  421. }
  422.  
  423. /******************************************************************************/
  424. /* Name : MoveList()
  425.  *
  426.  * Notes: This function is used to take the nodes that are in one list and
  427.  *        put them in another list.  It is important to note, that the
  428.  *        source list is NOT VALID AFTER THIS CALL.  Also, any nodes that
  429.  *        might already be in the destination list will be LOST.
  430.  */
  431. void nMoveList(struct nlist *slist, struct nlist *dlist)
  432. {
  433.   struct nnode *node;
  434.  
  435.   /* First, make the destination list point to its new head and tail
  436.    * nodes.  Also, init. the lh_Tail value.
  437.    */
  438.   dlist->head = slist->head;
  439.   dlist->tail = NULL;
  440.   dlist->tailpred = slist->tailpred;
  441.   dlist->nodes = slist->nodes;
  442.   /* Now, make the new tail node point to the list header. */
  443.   node = dlist->tailpred;
  444.   node->succ = (struct nnode *)&(dlist->tail);
  445.   /* Now, make the new head node point back at the list header. */
  446.   node = dlist->head;
  447.   node->pred = (struct nnode *)&(dlist->head);
  448. }
  449.  
  450. /******************************************************************************/
  451. /* Name : MoveNode()
  452.  *
  453.  */
  454. void nMoveNode(struct nlist *slist, struct nlist *dlist, struct nnode *node)
  455. {
  456.   nRemove(slist, node);
  457.   nEnqueue(dlist, node);
  458. }
  459.  
  460. /******************************************************************************/
  461. /* Name : AppendList()
  462.  *
  463.  * Notes: This function takes pointer to two list header, preList and
  464.  *        postList, and creates a list that is a combination of the
  465.  *        two, with the nodes in preList appearing first, followed by
  466.  *        the nodes of postList.  The resultant list is linked with the
  467.  *        header specified by preList.
  468.  */
  469. void nAppendList(struct nlist *prelist, struct nlist *postlist)
  470. {
  471.   struct nnode *lastOfPre = prelist->tailpred;
  472.   struct nnode *firstOfPost = postlist->head;
  473.  
  474.   struct nnode *lastOfPost;
  475.  
  476.   /* If the list that we were going to append to is empty, then the
  477.    * resultant list is just the list that we were going to append.
  478.    * The easy way to do this is to just copy the postlist to the
  479.    * prelist header.
  480.    */
  481.   if (prelist->nodes == 0) {
  482.     nMoveList(postlist, prelist);
  483.     nNewList(postlist);
  484.   }
  485.   /* If the list that we were going to append is empty, then we don't
  486.    * really have a chore to do.  Let's return to the caller now.
  487.    */
  488.   else if (postlist->nodes != 0) {
  489.     /* This is the point where this routine gets more than just a
  490.      * little complex.  This would make a good assignment for 3rd term,
  491.      * first year CS students.  It would weed the wimps out from the
  492.      * big dogs. :)
  493.      *
  494.      * There are actually two steps to this process.  The first step is
  495.      * to link the node at the end of the prelist to the node at the
  496.      * start of the postlist.  The second step is to link the node at
  497.      * the end of the postlist to the tail part of the list header.
  498.      */
  499.     lastOfPre->succ = firstOfPost;
  500.     firstOfPost->pred = lastOfPre;
  501.     lastOfPost = postlist->tailpred;
  502.     lastOfPost->succ = (struct nnode *)&(prelist->tail);
  503.     prelist->tailpred = lastOfPost;
  504.     prelist->nodes += postlist->nodes;
  505.     /* The last step is to make sure the user won't do something totally
  506.      * retarded and use the postlist.  We'll do that by clearing the
  507.      * list out.
  508.      */
  509.     nNewList(postlist);
  510.   }
  511. }
  512.  
  513. /******************************************************************************/
  514. /* Name : PrependList()
  515.  *
  516.  * Notes: This function takes pointer to two list header, preList and
  517.  *        postList, and creates a list that is a combination of the
  518.  *        two, with the nodes in preList appearing first, followed by
  519.  *        the nodes of postList.  The resultant list is linked with the
  520.  *        header specified by postList.
  521.  */
  522. void nPrependList(struct nlist *postList, struct nlist *preList)
  523. {
  524.   /* This is kind of a cheesy way to do this, but it works. :) The
  525.    * main reason that I did this routine this way is that it is a
  526.    * LOT less code, and I don't think that PrependList() will, in
  527.    * general, be used as much as AppendList().
  528.    */
  529.   nAppendList(preList, postList);
  530.   nMoveList(preList, postList);
  531.   nNewList(preList);
  532. }
  533.  
  534. /******************************************************************************/
  535. /* Name : SortList()
  536.  *
  537.  * Notes: This function is used to accomplish a slow and sleazy sorting of a
  538.  *        list by copying the list into a temporary list and sorting each
  539.  *        member as it gets copied.  Smaller Node Priorities get sorted to the
  540.  *        bottom.
  541.  */
  542. #define RADIX        32
  543. #define RADIX_DIVIDE    (1<<7)                    /* special case for -128 upto 127 */
  544. #define RADIX_OFFSET    (RADIX/2)                /* special case for -128 upto 127 */
  545.  
  546. /*
  547.  * the list contains data as follows:
  548.  *  es existieren mehr werte fuer niedrige zahlen und weniger werte fuer hohe zahlen:
  549.  *   100 werte im bereich 0-100
  550.  *   50 werte im bereich 100-200
  551.  *   25 werte im bereich 200-300
  552.  *  der groeszte wert ist nicht berechenbar und liegt in irgendeinem bereich
  553.  */
  554. void nSortListWeighted(struct nlist *list, int radix)
  555. {
  556.   struct nlist **bucket;                    /* Sorting buckets.    */
  557.   struct nnode *node = (struct nnode *)list;            /* Temporary list node pointer. */
  558.   int lcv;                            /* Local counter variable.   */
  559.   int radix_divide = 0;                        /* the greatest data in a node */
  560.  
  561.   /* allocate number of lists
  562.    */
  563.   if ((bucket = malloc(radix * sizeof(struct nlist *))) == 0)
  564.       return;
  565.  
  566.   for (lcv = radix - 1; lcv >= 0; lcv--)
  567.     if ((bucket[lcv] = malloc(sizeof(struct nlist))) == 0)
  568.         return;
  569.  
  570.   /* get the highest data-value
  571.    */
  572.   for (lcv = list->nodes; lcv > 0; lcv--) {            /* nodes !!! */
  573.     node = node->succ;
  574.     if (node->data > radix_divide)
  575.       radix_divide = node->data;
  576.   }
  577.   radix_divide = sqrt(radix_divide) / radix;            /* the worth */
  578.   radix_divide++;
  579.  
  580.   /* First, initialize all of the buckets that we will be sorting the
  581.    * nodes into.
  582.    */
  583.   for (lcv = radix - 1; lcv >= 0; lcv--)
  584.     nNewList(bucket[lcv]);
  585.  
  586.   /* Now, move every node out of the source list into the bucked that
  587.    * it belongs in.
  588.    */
  589.   node = list->head;                        /* Temporary list node pointer. */
  590.   for (lcv = list->nodes - 1; lcv >= 0; lcv--) {
  591.     register struct nnode *succnode = node->succ;
  592.     register int radix2 = sqrt(node->data) / radix_divide;
  593.  
  594.     nEnqueue(bucket[radix2], node);
  595.     node = succnode;
  596.   }
  597.  
  598.   /* Now merge all of the buckets together to form the final, sorted
  599.    * linked list.
  600.    */
  601.   nMoveList(bucket[radix - 1], list);
  602.   for (lcv = radix - 2; lcv >= 0; lcv--)
  603.     nAppendList(list, bucket[lcv]);
  604.  
  605.   for (lcv = radix - 1; lcv >= 0; lcv--)
  606.     free(bucket[lcv]);
  607.   free(bucket);
  608. }
  609.  
  610. /*
  611.  * the list contains data as follows:
  612.  *  die werte sind linear im daten-bereich verteilt
  613.  *  der groeszte wert ist nicht berechenbar und liegt in irgendeinem bereich
  614.  */
  615. void nSortListLinear(struct nlist *list, int radix)
  616. {
  617.   struct nlist **bucket;                    /* Sorting buckets.    */
  618.   struct nnode *node = (struct nnode *)list;            /* Temporary list node pointer. */
  619.   int lcv;                            /* Local counter variable.   */
  620.   int radix_divide = 0;                        /* the greatest data in a node */
  621.  
  622.   /* allocate number of lists
  623.    */
  624.   if ((bucket = malloc(radix * sizeof(struct nlist *))) == 0)
  625.       return;
  626.  
  627.   for (lcv = radix - 1; lcv >= 0; lcv--)
  628.     if ((bucket[lcv] = malloc(sizeof(struct nlist))) == 0)
  629.         return;
  630.  
  631.   /* get the highest data-value
  632.    */
  633.   for (lcv = list->nodes; lcv > 0; lcv--) {            /* nodes !!! */
  634.     node = node->succ;
  635.     if (node->data > radix_divide)
  636.       radix_divide = node->data;
  637.   }
  638.   radix_divide = radix_divide / radix;                /* the worth */
  639.   radix_divide++;
  640.  
  641.   /* First, initialize all of the buckets that we will be sorting the
  642.    * nodes into.
  643.    */
  644.   for (lcv = radix - 1; lcv >= 0; lcv--)
  645.     nNewList(bucket[lcv]);
  646.  
  647.   /* Now, move every node out of the source list into the bucked that
  648.    * it belongs in.
  649.    */
  650.   node = list->head;                        /* Temporary list node pointer. */
  651.   for (lcv = list->nodes - 1; lcv >= 0; lcv--) {
  652.     register struct nnode *succnode = node->succ;
  653.     register int radix2 = node->data / radix_divide;
  654.  
  655.     nEnqueue(bucket[radix2], node);
  656.     node = succnode;
  657.   }
  658.  
  659.   /* Now merge all of the buckets together to form the final, sorted
  660.    * linked list.
  661.    */
  662.   nMoveList(bucket[radix - 1], list);
  663.   for (lcv = radix - 2; lcv >= 0; lcv--)
  664.     nAppendList(list, bucket[lcv]);
  665.  
  666.   for (lcv = radix - 1; lcv >= 0; lcv--)
  667.     free(bucket[lcv]);
  668.   free(bucket);
  669. }
  670.  
  671. /*
  672.  * the list contains data as follows:
  673.  *  die werte sind linear im daten-bereich verteilt
  674.  *  der groeszte wert ist berechenbar und wird angegeben
  675.  */
  676. void nSortListLinearMax(struct nlist *list, int radix, int radix_divide)
  677. {
  678.   struct nlist **bucket;                    /* Sorting buckets.    */
  679.   struct nnode *node = (struct nnode *)list;            /* Temporary list node pointer. */
  680.   int lcv;                            /* Local counter variable.   */
  681.  
  682.   /* allocate number of lists
  683.    */
  684.   if ((bucket = malloc(radix * sizeof(struct nlist *))) == 0)
  685.       return;
  686.  
  687.   for (lcv = radix - 1; lcv >= 0; lcv--)
  688.     if ((bucket[lcv] = malloc(sizeof(struct nlist))) == 0)
  689.         return;
  690.  
  691.   /* get the highest data-value
  692.    */
  693.   radix_divide = radix_divide / radix;                /* the worth */
  694.   radix_divide++;
  695.  
  696.   /* First, initialize all of the buckets that we will be sorting the
  697.    * nodes into.
  698.    */
  699.   for (lcv = radix - 1; lcv >= 0; lcv--)
  700.     nNewList(bucket[lcv]);
  701.  
  702.   /* Now, move every node out of the source list into the bucked that
  703.    * it belongs in.
  704.    */
  705.   node = list->head;                        /* Temporary list node pointer. */
  706.   for (lcv = list->nodes - 1; lcv >= 0; lcv--) {
  707.     register struct nnode *succnode = node->succ;
  708.     register int radix2 = node->data / radix_divide;
  709.  
  710.     nEnqueue(bucket[radix2], node);
  711.     node = succnode;
  712.   }
  713.  
  714.   /* Now merge all of the buckets together to form the final, sorted
  715.    * linked list.
  716.    */
  717.   nMoveList(bucket[radix - 1], list);
  718.   for (lcv = radix - 2; lcv >= 0; lcv--)
  719.     nAppendList(list, bucket[lcv]);
  720.  
  721.   for (lcv = radix - 1; lcv >= 0; lcv--)
  722.     free(bucket[lcv]);
  723.   free(bucket);
  724. }
  725.  
  726. #endif                                /* LISTS_C */
  727.